#include "DynamicArrayl.h"
#include <iostream>
#include <cmath>
#include <limits.h>
namespace DARRAY
{
DynamicArray::~DynamicArray()
{

    for (int i = 0; i < size; i++)
    {
        freePtr(array[i]);
    }
    delete[] array;
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}
//!!
void DynamicArray::operator=(const DynamicArray &a)
{
    delete[] array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}

ElementType DynamicArray::operator[](int a)
{
    return FindByIndex(a);
}

DynamicArray::DynamicArray(): size(0), capacity(capacity)
{
    array = new ElementType[capacity];
    this->freePtr = nullptr;
    this->printPtr = nullptr;
    this->equalPtr = nullptr;

}

DynamicArray::DynamicArray(void (*freePtr)(ElementType), void (*printPtr)(ElementType),
                           int (*equalPtr)(ElementType, ElementType), size_t capacity) : size(0), capacity(capacity)
{
    array = new ElementType[capacity];
    this->freePtr = freePtr;
    this->printPtr = printPtr;
    this->equalPtr = equalPtr;
    
}

size_t DynamicArray::Size()
{
    return size;
}

void DynamicArray::Resize(size_t capacity)
{
    this->capacity = capacity;
    this->size = (size > capacity) ? capacity : size;
    ElementType *newp = new ElementType[capacity];
    for (size_t i = 0; i < size; i++)
    {
        newp[i] = array[i];
    }
    delete[] array;
    array = newp;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        Resize(2 * capacity);
    }
    array[size++] = element; // o(1)
}
void DynamicArray::Show()
{
    for (size_t i = 0; i < size; i++)
    {
        printPtr(array[i]);
    }
}

void DynamicArray::InsertHead(const ElementType &element)
{
    if (size >= capacity)
    {
        Resize(2 * capacity);
    }
    for (size_t i = size; i > 0; i--)
    {
        array[i] = array[i - 1];
    }
    array[0] = element;
    size++;
}

void DynamicArray::InsertIndex(int index, const ElementType &element)
{
    if (index < 0 || index > size)
    {
        return;
    }
    if (size >= capacity)
    {
        Resize(2 * capacity);
    }
    for (size_t i = size; i > index; i--)
    {
        array[i] = array[i - 1];
    }
    array[index] = element;
    size++;
}

void DynamicArray::RemoveByindex(int index)
{
    if (index < 0 || index >= size)
    {
        return;
    }
    for (size_t i = index; i < size - 1; i++)
    {
        array[i] = array[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(const ElementType &element)
{
    for (size_t i = 0; i < size; i++) // o(n^2)
    {
        if (equalPtr(array[i] , element)==2)
        {
            this->RemoveByindex(i);
            i--;
        }
    }
}

ElementType *DynamicArray::FindByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        return nullptr;
    }
    return &array[index];
}
//!!
DynamicArray DynamicArray::FindByElement(const ElementType &element)
{
    DynamicArray result(freePtr, printPtr, equalPtr);
    for (size_t i = 0; i < size; i++)
    {
        if (equalPtr(array[i] , element)==2)
        {
            result.InsertTail(array[i]);
        }
    }
    return result;
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    if (index < 0 || index >= size)
    {
        return;
    }
    array[index] = element;
}

void DynamicArray::UpdateByElement(const ElementType &oldv, const ElementType &newv)
{
    for (size_t i = 0; i < size; i++)
    {
        if (equalPtr( array[i] , oldv)==2)
        {
            array[i] = newv;
        }
    }
}

void DynamicArray::Duplicate()
{
    for (size_t i = 0; i < size; i++)
    {
        if (  equalPtr( array[i] , array[i - 1])==2)
        {
            RemoveByindex(i);
            i--;
        }
    }
}

// void DynamicArray::FastSort1(int start, int end)
// {
//     if (start >= end)
//     {
//         return;
//     }
//     size_t left = start;
//     size_t right = end;
//     ElementType temp = array[left];

//     while (left < right)
//     {
//         // 先右边动,找比基准值小
//         while (array[right] > temp && left < right)
//         {
//             right--;
//         }
//         // 把右边的值赋给左边空位
//         if (left < right)
//         {
//             array[left++] = array[right];
//         }
//         while (array[left] < temp && left < right)
//         {
//             left++;
//         }
//         if (left < right)
//             array[right--] = array[left];
//     }
//     array[left] = temp;
//     FastSort1(start, left - 1);
//     FastSort1(left + 1, end);
// }
// 归并算法
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    int first = 0;  // 当前数组
    int second = 0; // 传入的数组
    DynamicArray result(freePtr, printPtr, equalPtr);
    // 遍历两个数组
    while (first < this->size && second < a.size)
    {
        // if (this->array[first] <= a.array[second])
        if (equalPtr(this->array[first],a.array[second])==0)
        {
            result.InsertTail(array[first++]);
            
            std::cout << "小于";
            continue;
        }
        if (equalPtr(this->array[first], a.array[second])==2)
        {
            result.InsertTail(array[first]);
            first++;
            second++;
            continue;
        }
        
        if (equalPtr(this->array[first],a.array[second])==1)
        {
            result.InsertTail(a.array[second++]);
            std::cout << "大于";
            continue;
        }
        
        
    }
    while (first < this->size)
        result.InsertTail(array[first++]);

    while (second < a.size)
       result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::FindIntSctn(const DynamicArray &a)
{
    DynamicArray result(freePtr, printPtr, equalPtr);
    //
    int first = 0;
    int second = 0;
    while (first < size && second < a.size) // o(n)
    {
        if (  equalPtr(array[first] , a.array[second])==2)
        {
            result.InsertTail(array[first]);
            first++;
            second++;
        }
        // else if (array[first] > a.array[second])
        else if (equalPtr(array[first], a.array[second])==1)
        {
            second++;
        }
        // else if (array[first] < a.array[second])
        else if (equalPtr(array[first], a.array[second])==0)
        {
            first++;
        }
    }

    return result;
}

DynamicArray DynamicArray::FindUn(const DynamicArray &a)
{
    DynamicArray result(freePtr, printPtr, equalPtr);
    int first = 0;
    int second = 0;
    while (first < size && second < a.size)
    {
        if (equalPtr(array[first] , a.array[second])==2)
        {
            result.InsertTail(array[first]);
            second++;
            first++;
        }
        // else if (array[first] > a.array[second])
        else if (equalPtr(array[first], a.array[second])==1)
        {

            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while (first < this->size)
        result.InsertTail(array[first++]);

    while (second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::Finddefe(const DynamicArray &a)
{
    DynamicArray result(freePtr, printPtr, equalPtr);
    int first = 0;
    int second = 0;
    while (first < size && second < a.size)
    {
        if (equalPtr(array[first] , a.array[second])==2)
        {
            second++;
            first++;
        }
        // else if (array[first] > a.array[second])
        else if (equalPtr(array[first], a.array[second])==1)
        {

            result.InsertTail(a.array[second++]);
        }
        else
        {
            result.InsertTail(array[first++]);
        }
    }
    while (first < this->size)
        result.InsertTail(array[first++]);

    while (second < a.size)
        result.InsertTail(a.array[second++]);

    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)
{
    if (size != a.size)
    {
        return false;
    }
    for (int i = 0; i < size; i++)
    {  
        if (a.equalPtr(array[i],a.array[i])!=2)
        {
            return false;
        }
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while (left <= right)
    {
        size_t mid = left + (right - left) / 2;
        if (  equalPtr( array[mid] , element)==2)
        {
            return mid;
        }
        // else if (array[mid] > element)
        else if (equalPtr(array[mid], element)==1)
        {
            if (mid == 0)
            {
                return ULONG_MAX;
            }

            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    return ULONG_MAX;
}

bool DynamicArray::IsChild(const DynamicArray &a)
{
    // for (size_t i = 0; i < a.size; i++)
    // {
    //     if(FindByElement(a.array[i]).size==0)
    //     {
    //         return false;
    //     }
    // }

    // return true;

    int j = 0;
    for (int i = 0; i < size; i++)
    {
        if ( equalPtr( array[i] , a.array[j])==2)
        {

            j++;
            if (j==a.size)
            {
                return true;
            }
            
        }
    }
    return false;
}
// 滑动窗口
bool DynamicArray::IscntnsChild(const DynamicArray &a)
{
    for (int i = 0; i <= size - a.size; i++)
    {   
        if (Subsequence(i, a.size)== a)
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::Subsequence(int index, size_t size)
{
    if (index < 0 || index + size > this->size)
    {
        return DynamicArray(freePtr, printPtr, equalPtr);
    }
    DynamicArray result(freePtr, printPtr, this->equalPtr);
    for (int i = index; i < size + index; i++)
     {  ElementType temp=new ElementType;
        temp=array[i];
        result.InsertTail(temp);
    }
    return result;
}

void DynamicArray::Sort()
{
    FastSort(0, size - 1, 0, 2 * log2(size));
}

void DynamicArray::FastSort(size_t start, size_t end, size_t deepth, size_t maxdeep)
{
    if (start >= end)
    {
        return;
    }
    // 超过最大深度
    if (deepth > maxdeep)
    { // 改用插入排序
        InsertSort(start, end);
    }
    // 如果没有超过最大深度，继续快排分组
    else
    {
        size_t par = Partition(start, end);
        if (par != 0)
            FastSort(start, par - 1, deepth + 1, maxdeep);
        FastSort(par + 1, end, deepth + 1, maxdeep);
    }
}

void DynamicArray::InsertSort(size_t start, size_t end)
{
    for (size_t i = start; i <= end; i++)
    {
        size_t j = i;
        ElementType temp = array[i];
        for (; j > start; j--)
        {
            // if (array[j - 1] > temp)
            if (equalPtr(array[j - 1], temp)==1)
            {
                array[j] = array[j - 1];
            }
            else
            {
                break;
            }
        }

        array[j] = temp;
    }
}

size_t DynamicArray::Partition(size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[start];
    while (left < right)
    {
        // while (array[right] > temp && left < right)
        while (equalPtr(array[right], temp)==1 && left < right)
        {
            right--;
        }
        if (left < right)
        {
            array[left++] = array[right];
        }
        // while (array[left] < temp && left < right)
        while (equalPtr(array[left], temp)==0 && left < right)
        {
            left++;
        }
        if (left < right)
        {
            array[right--] = array[left];
        }
    }

    array[left] = temp;
    return left;
}
}